# Definition for a binary tree node.
import  collections
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        return self.dfs(root,sum) + self.pathSum(root.left,sum) + self.pathSum(root.right,sum)

    def dfs(self,root,sum):
        if not root:
            return 0
        count = 0
        if sum == root.val:
            count+=1
        count += self.dfs(root.left,sum-root.val)+self.dfs(root.right,sum-root.val)
        return count




m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(2)
m1.right.left = TreeNode(3)
m1.right.right = TreeNode(2)
s = Solution()

t = s.pathSum(m1,4)
print(t)
